1. Field of the Invention
This invention relates to systems and methods of determining interactions between bodies in a simulation space. More specifically, this invention relates to modeling interactions between molecules in solution.
2. Description of the Related Art
Molecular modeling belongs to a class of problems called N-body problems, where the behavior of each body in the system depends on its interaction with all of the other bodies in the system. Because it is impossible to calculate all of these interactions simultaneously, the only computational way to solve this problem is to loop over each possible pair of bodies, to determine how they affect each other. Thus, any selected body in a system containing N bodies requires looping over all of the other N-1 bodies to determine their affect on the selected body. In some embodiments the same process may then be repeated for all of the other N-1 bodies. Thus, there are N*(N-1), or N2-N interactions, which is written in Big-O notation as O(N2).
A common modification made to algorithms for solving N-body problems includes using cut-off radii, in which the contribution to the interaction of the chosen body from bodies outside the range of a cut-off radius are considered insignificant.
Using this method, the distance between each body pair in the system is checked at every iteration. Although calculating the distance is a relatively cheap operation in terms of computational efficiency, the necessity of iterating over every possible combination of bodies can become computationally expensive. One commonly used method of reducing the amount of computational time required to find interacting pairs of bodies is to cache the list of those bodies that interact. See Verlet, Computer ‘Experiments’ on Classical Fluids. II. Equilibrium Correlation Functions, Physical Review, 165:201-204 (1967), which is hereby incorporated by reference in its entirety.
One significant problem of using cached interacting pairs occurs because the list of cached interactions is not frequently updated. If the bodies change distances during or after an iteration, which is usually the case, the cached list of interacting bodies may not contain a full and accurate list of interacting pairs. The cached list may therefore lead to an inaccurate solution. Thus, a significant trade-off exists between the accuracy of the cached values and the frequency of the cache updates. Correcting this problem by updating the interaction table more often results in greater overhead (required to maintain the table) and a return to calculating all of the interactions (which were being avoided by the creation of the table). Caching infrequently creates situations in which the solution obtained may be inexact or incorrect.
One proposed solution includes widening the number of cached interactions to include non-interacting pairs, which may be expected to begin interacting within a certain number of iterations. Although the additional interactions that are being checked will slow down the iteration over the N atoms, this method reduces the number of full passes made through all possible interacting pairs. Further, this method does not solve the trade off between the cache and the update of the cache. See Thompson, Use of Neighbour Lists in Molecular Dynamics, Collaborative Computational Projects, 5, 8:20-28 (1983), which is hereby incorporated by reference in its entirety.
One available method to solve this problem is derived from a technique proposed based on spatially subdividing simulation space into separate equally-sized sections and then approximating a spherical cutoff by searching through a subsection of the subdivided areas. See Quentrec and Brot, New Method for Searching for Neighbors in Molecular Dynamics Computations, Journal of Computational Physics, 13:430-432 (1973), which is hereby incorporated by reference in its entirety. Although this technique did not demonstrate a significant gain in speed, it did show a reduction in memory usage. Further historical refinements to the method included a defined memory structure to improve access times for each subdivision and the cells contained. See Leach, Molecular Modeling: Principles and Applications, Addison Wesley Longman, Essex, England (1996), which is hereby incorporated by reference in its entirety. Still other approaches to these methods were based upon neighbor lists. See Verlet, supra; and Thompson, supra.